#ifndef _CXX_SKIP_LIST_H
#define _CXX_SKIP_LIST_H
#include "cxx_list.h"
#include <stack>
#include <stdlib.h>
namespace ds_cxx
{
template<typename V>
struct SkipListNode
{
    SkipListNode<V>* right;
    SkipListNode<V>* next;
    int key;
    List<V> data;
    SkipListNode(int key,V _data,SkipListNode<V>* right=nullptr,SkipListNode<V>* next=nullptr)
    : key(key),right(right),next(next){
        data.PushBack(_data);
    }
    ~SkipListNode(){ right = next = nullptr;}
};

template<typename V>
class SkipList
{
public:
    typedef SkipListNode<V>* SKLNodePtr;
    SkipList() : head(nullptr),level(0),size(0){}
    ~SkipList()
    {
        if(head && level > 0 && size > 0)
        {
            SKLNodePtr cur = head;
            while(cur)
            {
                SKLNodePtr nxt = cur->next;
                while(cur)
                {
                    SKLNodePtr rgh = cur->right;
                    delete(cur);
                    cur = rgh;
                }
                cur = nxt;
            }
        }
        level = size = 0;
    }
public:
    bool Search(int key)
    {
        if(!head || level == 0 || size == 0) return false;
        SKLNodePtr cur = head;
        while(cur)
        {
            while(cur->right && cur->right->key < key)
            {
                cur = cur->right;
            }
            if(cur->right && cur->right->key == key)
            {
                return true;
            }
            cur = cur->next;
        }
        return false;
    }
    void Add(int key,V data)
    {
        //search exist key,add data list
        {
            bool bSearch = false;
            SKLNodePtr cur = head;
            while(cur)
            {
                while(cur->right && cur->right->key < key)
                {
                    cur = cur->right;
                }
                if(cur->right && cur->right->key == key)
                {
                    bSearch = true;
                    cur->right->data.PushBack(data);
                }
                cur = cur->next;
            }
            if(bSearch) return;
        }
        SKLNodePtr cur = head;
        //暂时使用标准库
        std::stack<SKLNodePtr> stk; // 记录关联路径
        while(cur)
        {
            while(cur->right && cur->right->key < key)
            {
                cur = cur->right;
            }
            stk.push(cur);
            cur = cur->next;
        }
        bool bInsert = true;
        SKLNodePtr nxt = nullptr;
        while(bInsert && !stk.empty())
        {
            SKLNodePtr back = stk.top();
            stk.pop();

            SKLNodePtr node = new SkipListNode<V>(key,data,back->right,nxt);
            back->right = node;
            bInsert = rand()%2 == 0;
            nxt = node;
        }
        if(bInsert)
        {
            SKLNodePtr node = new SkipListNode<V>(key,data,nullptr,nxt);
            SKLNodePtr dummy = new SkipListNode<V>(-1,V(),node,head);
            head = dummy;
            ++level;
        }
        ++size;
    }
    bool Erase(int key,bool bAll = false)
    {
        if(!head || level == 0 || size == 0) return false;
        SKLNodePtr cur = head;
        bool bErase = false;
        while(cur)
        {
            while(cur->right && cur->right->key < key)
            {
                cur = cur->right;
            }
            if(cur->right && cur->right->key == key)
            {
                if(bAll)
                {
                    SKLNodePtr rgh = cur->right->right;
                    cur->right->data.Clear();
                    delete(cur->right);
                    cur->right = rgh;
                }
                else
                {
                    cur->right->data.PopBack();
                    if(cur->right->data.Empty())
                    {
                        SKLNodePtr rgh = cur->right->right;
                        delete(cur->right);
                        cur->right = rgh;
                    }
                }
                bErase = true;
            }
            cur = cur->next;
        }
        if(bErase) --size;
        return bErase;
    }
    unsigned int Depth() { return level; }
    unsigned int Size() { return size; }
private:
    SKLNodePtr head;
    unsigned int level;
    unsigned int size;
};
}

#endif